package org.example.algorithm.sliding;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

public class FindAnagramsSolution {

    public static void main(String[] args) {
        String s = "aabb";
        String p = "bb";
        FindAnagramsSolution solution = new FindAnagramsSolution();
        List<Integer> res = solution.findAnagrams(s, p);
        System.out.println(res);
    }
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> res = new ArrayList<>();
        if (s.length() < p.length()) {
            return res;
        }
        HashMap<Character, Integer> map = new HashMap<>();
        for (int i=0;i<p.length();i++) {
            map.put(p.charAt(i), map.getOrDefault(p.charAt(i), 0) + 1);
        }

        HashMap<Character, Integer> charMap = new HashMap<>();
        int left = 0;
        int right = 0;
        int count = 0;
        while (right < s.length()) {
            char rightChar = s.charAt(right);
            right++;
            if (map.containsKey(rightChar)) {
                count++;
                charMap.put(rightChar, charMap.getOrDefault(rightChar, 0) + 1);
                //收缩窗口
                while(map.get(rightChar) < charMap.get(rightChar) && left < right) {
                    char leftChar = s.charAt(left);
                    if (map.containsKey(leftChar)) {
                        charMap.put(leftChar, charMap.getOrDefault(leftChar, 0) - 1);
                        count--;
                    }
                    left++;
                }
                if (count == p.length()) {
                    res.add(left);
                }
            } else {
                left = right;
                count = 0;
                charMap.clear();
            }
        }
        return res;
    }
}
